"""
2554. 从一个范围内选择最多整数 I
已解答
中等
相关标签
相关企业
提示
给你一个整数数组 banned 和两个整数 n 和 maxSum 。你需要按照以下规则选择一些整数：

被选择整数的范围是 [1, n] 。
每个整数 至多 选择 一次 。
被选择整数不能在数组 banned 中。
被选择整数的和不超过 maxSum 。
请你返回按照上述规则 最多 可以选择的整数数目。



示例 1：

输入：banned = [1,6,5], n = 5, maxSum = 6
输出：2
解释：你可以选择整数 2 和 4 。
2 和 4 在范围 [1, 5] 内，且它们都不在 banned 中，它们的和是 6 ，没有超过 maxSum 。
示例 2：

输入：banned = [1,2,3,4,5,6,7], n = 8, maxSum = 1
输出：0
解释：按照上述规则无法选择任何整数。
示例 3：

输入：banned = [11], n = 7, maxSum = 50
输出：7
解释：你可以选择整数 1, 2, 3, 4, 5, 6 和 7 。
它们都在范围 [1, 7] 中，且都没出现在 banned 中，它们的和是 28 ，没有超过 maxSum 。


提示：

1 <= banned.length <= 104
1 <= banned[i], n <= 104
1 <= maxSum <= 109
"""
class Solution(object):
    def maxCount(self, banned, n, maxSum):
        """
        :type banned: List[int] 不能选择
        :type n: int 取值范围[1,n]
        :type maxSum: int 最大和
        :rtype: int
        """
        banned = set(banned)
        banned = list(banned)
        banned.sort()
        print(banned)
        dp = [0] * int(1e4 + 1)
        for i in banned:
            dp[i] = 1
        ans = 0
        for i in range(1,n+1):
            if dp[i] == 1:
                continue
            else:
                if maxSum >= i:
                    ans+=1
                    maxSum -= i
                else:
                    break
        return ans


    def maxCount_res1(self, banned: List[int], n: int, maxSum: int) -> int:
        ans, s = 0, set(banned)
        for i in range(1, n + 1):
            if i > maxSum: break
            if i not in s:
                maxSum -= i
                ans += 1
        return ans


if __name__ == '__main__':
    banned = [1,6,5,5]
    n = 5
    maxSum = 6
    print(Solution().maxCount(banned,n,maxSum))
